﻿/************************************************************************
 * AIDE - Automata Identification Engine
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     AIDE\Utils\SortUtil.cs
 * Description  :     Some function utility for sorting/ordering numbers
 * Change log   :     -Dec 2012: initil version
 * To Do        :
 ************************************************************************/
using System;
using System.Collections.Generic;

namespace AIDE.Utils
{
    /// <summary>
    /// Some function utility for sorting/ordering numbers
    /// </summary>
    internal class SortUtil
    {
        /// <summary>
        ///  Find the N minimum (distinct) number of a list
        ///  Note: it is not optimal solution!
        /// </summary>
        /// <param name="N">number of minimum nubers to be found</param>
        /// <param name="theList">the whole list</param>
        /// <returns>the list of minimum numbers</returns>
        public static List<int> Find(int N, List<int> theList)
        {
            List<int> minList = new List<int>();
            int numberOfFound = 0;

            minList = new List<int>();
            for (int i = 0; i < theList.Count; i++)
            {
                if (numberOfFound < N)
                {
                    if (numberOfFound == 0)
                    {
                        minList.Add(theList[i]);
                        numberOfFound++;
                        continue;
                    }
                    // Add to the end
                    else if (minList[numberOfFound - 1] < theList[i])
                    {
                        minList.Add(theList[i]);
                        numberOfFound++;
                        continue;
                    }

                    int k;
                    for (k = 0; k < numberOfFound; k++)
                    {
                        if (theList[i] < minList[k])
                        {
                            minList.Insert(k, theList[i]);
                            numberOfFound++;
                            break;
                        }
                        // It already has this number
                        else if (minList[k] == theList[i])
                            break;
                    }
                }
                else
                {
                    if (!(theList[i] > minList[N - 1]))
                    {
                        // We have to insert it in to the list
                        int k;
                        for (k = 0; k < N; k++)
                        {
                            // Insert it here
                            if (theList[i] < minList[k])
                            {
                                minList.Insert(k, theList[i]);
                                minList.RemoveAt(N);
                                break;
                            }
                            // It already has this number
                            else if (minList[k] == theList[i])
                                break;
                        }
                    }
                }
            }
            return minList;
        }
    }
}
